//
// Created on 2021/5/22.
// Modified from https://blog.csdn.net/zhangxiao93/article/details/51459743
//

// C++ 实现二叉排序平衡树


#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

template<typename T>
class AVLNode   //平衡树的结点
{
public:
    T Key;
    AVLNode *left;
    AVLNode *right;
    AVLNode(): AVLNode(0) {}   // C11委托构造函数
    AVLNode(T k)  {Key = k; left = nullptr; right = nullptr;}
};

template<typename T>
class AVLTree
{
public:
    typedef AVLNode<T> AVLNode;         //类型定义
    AVLNode *avlRoot;                   //私有数据结构
private:
    int privateHeight(const AVLNode *root)   //求树的高度
    {
        if(root == nullptr)
            return 0;
        return max(privateHeight(root->left), privateHeight(root->right)) + 1;

    }
    int privateDiff(const AVLNode*root)      //高度差（平衡因子）
    {
        return (privateHeight(root->left) - privateHeight(root->right));
    }

    /*
     AVL4种旋转：左左，左右，右右，右左
        X 为插入位置节点到根节点的路径上平衡条件被改变的节点中, 最深的那个节点, 通过递归返回的方式找到
        左左：插入点位于X的左孩子节点的左子树
        左右：插入点位于X的左孩子节点的右子树
        右右：插入点位于X的右孩子节点的右子树
        右左：插入点位于X的右孩子节点的左子树
     */

    AVLNode *LL_Rotation(AVLNode *root) //left-left rotation
    {
        AVLNode *temp = root->left;
        root->left = temp->right;
        temp->right = root;
        return temp;
    }

    AVLNode *RR_Rotation(AVLNode *root) //right-right rotation
    {
        AVLNode *temp = root->right;
        root->right = temp->left;
        temp->left = root;
        return temp;
    }

    //双旋转
    AVLNode *LR_Rotation(AVLNode *root)  //left-right rotation
    {
        AVLNode *temp = root->left;
        root->left = LL_Rotation(temp);
        return RR_Rotation(root);
    }

    AVLNode *RL_Rotation(AVLNode *root)  //right-left rotation
    {
        AVLNode *temp = root->right;
        root->right = RR_Rotation(temp);
        return LL_Rotation(root);
    }

    AVLNode *privateBalance(AVLNode *root)  //平衡操作
    {
        int balanceFactor = privateDiff(root);  //diff用来计算平衡因子（左右子树高度差）
        if (balanceFactor == 2)  //左子树高于右子树时
        {
            if (privateDiff(root->left) >= 1)  //左左外侧
                root = LL_Rotation(root);
            else if(privateDiff(root->left) <= -1) //左右内侧
                root = LR_Rotation(root);
        }
        else if (balanceFactor == -2)  //右子树高于左子树时
        {
            if (privateDiff(root->right) >= 1)  //右左内侧
                root = RL_Rotation(root);
            else if(privateDiff(root->right) <= -1) //右右外侧
                root = RR_Rotation(root);
        }
        return root;
    }

    AVLNode *privateInsert(AVLNode *&root, const T &k)  //插入的内部实现
    {
        if(root == nullptr)
            root = new AVLNode(k);
        else if(k < root->Key)
        {
            root->left = privateInsert(root->left, k);
            root = privateBalance(root);
        }
        else if(k > root->Key)
        {
            root->right = privateInsert(root->right, k);
            root = privateBalance(root);
        }
        return root;
    }

    //中序遍历的两种重载
    void privateInorderTraversal(const AVLNode *root)  //直接输出遍历
    {
        if (root == nullptr)
            return;
        privateInorderTraversal(root->left);
        cout << root->Key << " ";
        privateInorderTraversal(root->right);
    }

    void privateInorderTraversal(const AVLNode *root, std::vector<T> &vec)  //结果保存到vec数组中
    {
        if(root == nullptr)
            return;
        privateInorderTraversal(root->left, vec);
        vec.push_back(root->val);
        privateInorderTraversal(root->right, vec);
    }

    bool isNodeWithTwoChild(const AVLNode *root)  //判断是否有两个孩子
    {
        return ((root->left != nullptr) && (root->right != nullptr));
    }


    const AVLNode* privateSearch(const AVLNode *root, const T &k)  //查找的内部实现
    {
        if(root == nullptr)
            return nullptr;

        if(k == root->Key)
            return root;
        else if(k > root->Key)
            return privateSearch(root->right, k);
        else
            return privateSearch(root->left, k);
    }

    void privateDeleteTree(AVLNode *root) //删除树的所有节点
    {
        if(root == nullptr)
            return;
        privateDeleteTree(root->left);
        privateDeleteTree(root->right);
        if(root)
            delete root;
        root = nullptr;
        return;
    }

    AVLNode* privateDeleteNode(AVLNode * root, const T& k)  //删除节点
    {
        if (root == nullptr)
            return root;
        if (!Search(k)) //查找删除元素是否存在
        {
            cerr << "Error: the Key not found!" << endl;
            return root;
        }

        if (k == root->Key)//根节点
        {
            if (isNodeWithTwoChild(root)) //左右子树都非空
            {
                if (privateDiff(root) > 0)   //左子树更高，在左边删除
                {
                    root->Key = treeMaxNode(root->left)->Key;         //以左子树的最大值替换当前值
                    root->left = privateDeleteNode(root->left, root->Key);   //删除左子树中已经替换上去的节点
                }
                else    //右子树更高，在右边删除
                {
                    root->Key = treeMinNode(root->right)->Key;
                    root->right = privateDeleteNode(root->right, root->Key);
                }
            }
            else    //有一个孩子、叶子节点的情况合并
            {
                //if (!__isLeaf(root))
                AVLNode * tmp = root;
                root = (root->left) ? (root->left) :( root->right);
                delete tmp;
                tmp = NULL;
            }
        }//end-if
        else if (k < root->Key) //往左边删除
        {
            root->left = privateDeleteNode(root->left, k);   //左子树中递归删除
            //判断平衡的条件与在插入时情况类似
            if (privateDiff(root) < -1)  //不满足平衡条件，删除左边的后，右子树变高
            {
                if (privateDiff(root->right) > 0)
                {
                    root = RL_Rotation(root);
                }
                else
                {
                    root = RR_Rotation(root);
                }
            }
        }//end else if
        else
        {
            root->right = privateDeleteNode(root->right, k);
            if (privateDiff(root) > 1)  //不满足平衡条件
            {
                if (privateDiff(root->left) < 0)
                {
                    root = LR_Rotation(root);
                }
                else
                {
                    root = LL_Rotation(root);
                }
            }
        }
        return root;
    }
    AVLNode *treeMinNode(AVLNode *root)  //求当前根节点最小（一路向左）
    {
        if(root == nullptr)
            return nullptr;
        else if(root && root->left == nullptr)
            return root;
        else
            treeMinNode(root->left);
    }
    AVLNode *treeMaxNode(AVLNode *root)  //求当前根节点的最大（一路向右）
    {
        if(root == nullptr)
            return nullptr;
        else if(root && root->right == nullptr)
            return root;
        else
            treeMinNode(root->right);
    }

public:
    AVLTree() {avlRoot = nullptr;}      //默认构造函数
    AVLTree(const std::vector<T> &vec)  //构造函数，容器构造
    {
        avlRoot = nullptr;
        for(auto i=0; i<vec.size(); i++)
        {
            privateInsert(avlRoot, vec[i]);
        }
    }
    AVLTree(const T *arr, size_t len)  //构造函数，数组构造
    {
        avlRoot = nullptr;
        for(std::size_t i=0; i<len; i++)
        {
            privateInsert(avlRoot, arr[i]);
        }
    }
    void InorderTraversal()  //中序遍历外部接口
    {
        privateInorderTraversal(avlRoot);
    }
    void InorderTraversal(std::vector<T> &vec)  //中序遍历外部接口重载2
    {
        privateInorderTraversal(avlRoot, vec);
    }
    bool Delete(const T &k)  //删除节点的外部接口
    {
        return privateDeleteNode(avlRoot, k) != nullptr;
    }
    bool Insert(const T &k)  //插入节点的外部接口
    {
        return privateInsert(avlRoot, k) != nullptr;
    }
    bool IsEmpty() {return (avlRoot == nullptr);} //判断树空
    bool Search(const T &k)  //查询外部接口
    {
        return privateSearch(avlRoot, k) != nullptr;
    }
    ~AVLTree() {privateDeleteTree(avlRoot);} //析构函数删除树中所有节点
}; //class AVLTree

